﻿#pragma once

namespace micro {


namespace utils
{


template<class T>
class QTreeEqualHelper
{
public:
	static bool IsEqual(T & t1, T & t2){ return t1 == t2; }
	static bool IsLess(T & t1, T & t2) { return t1 < t2;  }
	static bool IsLessEqual(T & t1, T & t2) { return t1 <= t2;  }
 

};


template<class T, class TEqual = QTreeEqualHelper<T> > 
class QTree
{

protected:
	class Node
	{
	public:

		T info;
		Node * left, *right;
		Node(T  t, Node * left = nullptr, Node * right = nullptr):info(t), left(left), right(right){}
		~Node()
		{ 
			if(left) delete left;
			if (right) delete right;
		}

	} * m_root;

 
public:

	QTree(){  m_root = nullptr; }
	~QTree()
	{
		RemoveAll();
		
	};


	 
	void RemoveAll()
	{
		if(m_root)
		{
			//recursiv
			delete m_root;
			m_root = nullptr;
		}

	}


	bool IsEmpty(){ return nullptr==m_root;}
	
	bool Get(T& t ) 
	{ 
		if (nullptr == m_root)
			return false;
	}

	 
	void Add(T & t)
	{
		Add(t, m_root);
	}

	bool Find(T & t)
	{
		return Find(t, m_root);
	}
private:

	void Add(T & t, Node * &p )
	{
		if(nullptr == p)
		{
			p = new Node(t);
			return;
		}

		if( TEqual::IsEqual(t, p->info) )
			return;

		if(  TEqual::IsLess(t, p->info) )
			Add(t, p->left);
		else
			Add(t, p->right);
	}

	bool Find(T & t, Node * p )
	{
		if(nullptr == p)
			return false;
		
		if( TEqual::IsEqual(t, p->info) )
			return true;

		if(  TEqual::IsLess(t, p->info) )
			return Find(t, p->left);

		return 	Find(t, p->right);
	}
	


};

 

}//utils

}//micro